Chapter 2: Abstract Data Types

Data

• The representation of information in a manner suitable for communication or analysis by humans or machines

• Data are the nouns of the programming world:

– The objects that are manipulated

– The information that is processed

• Example: You want to develop database software that keeps information and records of all employees in a certain company. The information that you want to store and manipulate is – employee name, age, designation, salary etc.

Data Types:

• Classification of data categorized by supported elements and operations of those elements. Example: integer, character, float etc.

• Atomic or primitive data type: Data type with single non-decomposable data items. Example: int, float, char.

• Composite type: Data type whose elements are composed of multiple data items. Example: tuple, array, object of any class.

• Structured composite type: An organized collection of components in which the organization determines the means of accessing individual data components or subsets of the collection. Example: sorted array.

Information Hiding:

• Information Hiding is the idea that only information (data, access routines, etc) that need to be seen, are. If any type of information can be centralized and hidden away from the outside program, this is good, for the simple fact it simplifies the rest of the program.

• The idea starts in the design stage of a program, and goes right through the construction phase and to the testing phase.

• How do we hide information? By dividing a program up into modules, you allow specific information to be hidden away. This can be particular data, complex logic, or specific implementation details of a piece of software.

Advantages of Information Hiding:

• Easier to reuse code
• Easier to isolate bugs
• Easier construction - with small, well defined sections
• Easier abstraction (get closer to the problem)
• Allows isolation of areas likely to change
• Allows hiding of complex data or logic
• Allows hiding programming language level operations

Data Abstraction and Encapsulation

• Data abstraction is the process of organizing access to a program's data (e.g., arranging variable declarations and methods for accessing data into class definitions).

• Data encapsulation, sometimes referred to as data hiding, is the mechanism by which the implementation details of a class are kept hidden from the user.

Abstract Data Type

• A specification of a set of data and the set of operations that can be performed on the data. Such a data type is abstract in the sense that it is independent of various concrete implementations.

• Example: all of Java’s built-in types, such as int, double, char are all ADTs. You can declare variables of these types without understanding the underlying implementation details. You can initialize, modify, access the information held by these variables via specific operations.

• You can create your own ADT by using class mechanism.

Data Structure:

• A collection of data elements whose logical organization reflects a relationship among the elements

• It is best to design data structures with ADTs.

Basic Operations on Encapsulated Data

• A constructor is an operation that creates a new instance (object) of the data type.

• Transformers (sometimes called mutators) are operations that change the state of one or more of the data values. In other words, these are called setter methods.

• An observer is an operation that allows us to observe the state of one or more of the data values with out changing them. In other words, these are called getter methods.

• An iterator is an operation that allows us to process all the components in a data structure sequentially.

Data Level of an ADT

• Logical (or abstract) level: Abstract view of the data values (the domain) and the set of operations to manipulate them.

• Application (or user) level: Here the application programmer uses the ADT to solve a problem.

• Implementation level: A specific representation of the structure to hold the data items, and the coding of the operations in a programming language.

Communication between Implementation Level and Application Level

Java’s Built-in Types

The Java Class Construct

• Can be a mechanism for creating composite data types.

• Is composed of named data fields (class and instance variables) and methods.

• Is unstructured because the meaning is not dependent on the ordering of the members.

Accesses a field value

Creates a new instance of class Circle

Assignment Statement: Primitive Type Vs Object

Consequences of Using References

•

System.out.println(c1);

c2. changeValue();

System.out.println(c1);

Aliases: We may have two references/ names for the same object.

• Garbage Memory space that has been allocated to a program but can no longer be accessed by a program.

Parameter Passing in Java

• All Java arguments are passed by value.

• If the variable is of a primitive type, the actual value (int, double, and so on) is passed to the method.

• If it is a reference type, then the reference that it contains is passed to the method.

Java Interfaces

• All variables declared in an interface must be final, static variables.

• All methods declared in an interface must be abstract.

• Abstract method: A method declared in a class or an interface without a method body.

Interfaces can be used in the following ways:

• As a contract— Capture an abstract view of a class or classes in an interface.

• To share constants—Define constants in an interface and have each class implement the interface.

• To replace multiple inheritance—A class can extend one superclass, but it can implement many interfaces.

• To provide a generic type mechanism—In Chapter 3 you learn how to use the Java interface construct to provide generic structures.

Array Vs Class

An array differs from a class in the following three ways:

• An array is a homogenous structure, whereas classes are heterogeneous structures.

• A component of an array is accessed by its position in the structure, whereas a component of a class is accessed by an identifier (the name).

• Because array components are accessed by position, an array is a structured composite type.

Example of Combining Multiple Objects

Suppose we define:

public class Point

{

public int xValue;

public int yValue;

}

Then, we could define a new circle class as:

public class NewCircle

{

public Point location;

public float radius;

public boolean solid;

}

An Array of Objects

Example of Two Dimensional Array